package com.LeeCode;

/**
 * 最大化游戏分数的最小值
 */

public class Code3449 {
    public static void main(String[] args) {
        int[] points = {2, 4};
        int m = 3;
        System.out.println(new Code3449().maxScore(points, m));

    }

    public long maxScore(int[] points, int m) {
        int mn = Integer.MAX_VALUE;
        for (int p : points) {
            mn = Math.min(mn, p);
        }
        long left = 0;
        long right = (long) (m + 1) / 2 * mn + 1;
        while (left + 1 < right) {
            long mid = (left + right) >>> 1;
            if (check(mid, points, m)) {
                left = mid;
            } else {
                right = mid;
            }
        }
        return left;
    }

    private boolean check(long low, int[] points, int m) {
        int n = points.length;
        int left = m; // 剩余操作次数
        int pre = 0;
        for (int i = 0; i < n; i++) {
            int k = (int) ((low - 1) / points[i]) + 1 - pre; // 还需要操作的次数
            if (i == n - 1 && k <= 0) { // 最后一个数已经满足要求
                break;
            }
            k = Math.max(k, 1); // 至少要走 1 步
            left -= k * 2 - 1; // 左右横跳
            if (left < 0) {
                return false;
            }
            pre = k - 1; // 右边那个数顺带操作了 k-1 次
        }
        return true;
    }
}
